package ua.mykola.graph;

import java.util.PriorityQueue;
import java.util.Set;

public class KruskalMST {

	private Graph graph;
	private Graph mst = new AdjListGraph();

	public KruskalMST(Graph graph) {
		this.graph = graph;
	}

	public void traverse() {
		PriorityQueue<Edge> edgesToTraverse = new PriorityQueue<Edge>(11,
				new EdgeWeightComparator());
		edgesToTraverse.addAll(graph.getEdges());
		while (!edgesToTraverse.isEmpty()) {
			Edge smallestEdge = edgesToTraverse.poll();
			DFS dfs = new DFS(mst, smallestEdge.getVertexA());
			dfs.traverse();
			if (!dfs.hasPathTo(smallestEdge.getVertexB())) {
				mst.addEdges(smallestEdge);
			}
		}

	}

	public Set<Edge> getMSTEdges() {
		return mst.getEdges();
	}

	public int getMSTWeight() {
		int weight = 0;
		for (Edge edge : mst.getEdges()) {
			weight += edge.getWeight();
		}
		return weight;
	}
}
